package com.acyouzi.leetcode.greedy;

import java.util.*;

/**
 * 17/9/6 10:24
 *
 * @author sunxu
 */
public class SplitArray {
//  // 超时
//  public static boolean isPossible(int[] nums) {
//    PriorityQueue<Set<Integer>> list = new PriorityQueue<>(new Comparator<Set<Integer>>() {
//      @Override
//      public int compare(Set<Integer> o1, Set<Integer> o2) {
//        return o1.size() > o2.size() ? 1:-1;
//      }
//    });
//    for (int num : nums){
//      boolean flag = true;
//      for (Set<Integer> set : list){
//        if (set.contains(num-1) && !set.contains(num)) {
//          set.add(num);
//          flag = false;
//          break;
//        }
//      }
//      if (flag) {
//        HashSet<Integer> set = new HashSet<>();
//        set.add(num);
//        list.add(set);
//      }
//    }
//    for (Set<Integer> set : list) {
//      if (set.size() < 3) return false;
//    }
//    return true;
//  }


  public boolean isPossible(int[] nums) {
    // 存储出现的次数
    Map<Integer, Integer> freq = new HashMap<>();
    // 存储到当前位置结尾的队列长度
    Map<Integer, Integer> appendfreq = new HashMap<>();
    for (int i : nums) freq.put(i, freq.getOrDefault(i,0) + 1);
    for (int i : nums) {
      if (freq.get(i) == 0) continue;
      else if (appendfreq.getOrDefault(i,0) > 0) {
        // 能加入的原有队列，则加入
        appendfreq.put(i, appendfreq.get(i) - 1);
        appendfreq.put(i+1, appendfreq.getOrDefault(i+1,0) + 1);
      }
      else if (freq.getOrDefault(i+1,0) > 0 && freq.getOrDefault(i+2,0) > 0) {
        // 如果当前元素能够与他的随后两个元素连成三个(说明能够构成队列)
        freq.put(i+1, freq.get(i+1) - 1);
        freq.put(i+2, freq.get(i+2) - 1);
        // 以 i + 2 结尾的队列 + 1
        appendfreq.put(i+3, appendfreq.getOrDefault(i+3,0) + 1);
      }
      else return false;
      freq.put(i, freq.get(i) - 1);
    }
    return true;
  }


//  public static void main(String[] args) {
//    isPossible(new int[]{1,2,3,3,4,5});
//  }
}
